package com.huawei.ju;

/**
 * @description https://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3?tpId=295&tqId=1073463&ru=/exam/intelligent&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fintelligent%3FquestionJobId%3D10%26tagId%3D21014
 *  给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
 * 注意是节点的编号而非节点的数值。
 * @author wj
 * @date 2023-10-04
 */
public class BM14 {

  public static void main(String[] args) {
    BM14 bm14 = new BM14();
    ListNode listNode1 = new ListNode(1);
//    ListNode listNode2 = new ListNode(4);
//    ListNode listNode3 = new ListNode(6);
//    ListNode listNode4 = new ListNode(3);
//    ListNode listNode5 = new ListNode(7);
    ListNode listNode2 = new ListNode(2);
    ListNode listNode3 = new ListNode(3);
    ListNode listNode4 = new ListNode(4);
    ListNode listNode5 = new ListNode(5);
    ListNode listNode6 = new ListNode(6);
    listNode5.next = listNode6;
    listNode4.next = listNode5;
    listNode3.next = listNode4;
    listNode2.next = listNode3;
    listNode1.next = listNode2;
    ListNode listNode = bm14.oddEvenList(listNode1);
    System.out.println(listNode);
  }

  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   *
   * @param head ListNode类
   * @return ListNode类
   */
  public ListNode oddEvenList (ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }
    ListNode preNode = null;
    ListNode afterNode = null;
    boolean flag = true;
    while (head != null) {
      ListNode tempNode = new ListNode(head.val);
      if (flag) {
        tempNode.next = preNode;
        preNode = tempNode;
        flag = false;
      } else {
        tempNode.next = afterNode;
        afterNode = tempNode;
        flag = true;
      }
      head = head.next;
    }
    ListNode resultNode = null;
    while (afterNode != null) {
      ListNode tempNode1 = new ListNode(afterNode.val);
      tempNode1.next = resultNode;
      resultNode = tempNode1;
      afterNode = afterNode.next;
    }
    while (preNode != null) {
      ListNode tempNode2 = new ListNode(preNode.val);
      tempNode2.next = resultNode;
      resultNode = tempNode2;
      preNode = preNode.next;
    }
    // 1,4,6,3,7 -> 1,6,7,4,3
    return resultNode;
  }

  public static class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
  }
}
